I. Field of the Invention
The present invention relates to data transmission. More particularly, the present invention relates to a novel and improved method for preventing message collisions in a half-duplex communication system.
II. Description of the Related Art
In a half-duplex communication system, multiple communicating devices are connected to a single communication channel. One such system is a fax communication system in which two fax machines send messages across a telephone line. Half-duplex devices such as fax machines are capable of only transmitting or receiving messages at any particular instant. These devices cannot transmit and receive data simultaneously. If two devices transmit signals toward each other simultaneously and neither device is listening, the devices will not receive the other's message. This event is known as a message collision.
Most half-duplex communication systems are designed to minimize message collisions to improve the quality of the communications. These systems employ a variety of schemes to avoid message collisions. Some of these schemes require a certain quality in the communication channel. As the communication channel deteriorates, there may be an increased likelihood of message collisions. Other schemes use special timing and synchronization to avoid message collisions. For these schemes, increased delays in the communication channel may cause the system to fail.
A fax communication system is an example of a half-duplex communication system which relies on the timing and synchronization between the two communicating fax machines to avoid message collisions. The fax machines communicate with each other through a standard public switched telephone network (PSTN) channel which has known channel quality and delay characteristics. When a non-standard PSTN channel, such as a digital communication system or a satellite link, is inserted between the two fax machines the increased transmission delays can cause the fax interactions to fail because of message collisions.
A digital communication system or satellite link is incorporated with the half-duplex communication system to extend the range of coverage, allow mobility in the communicating devices, and increase interconnectivity between different communicating devices. An exemplary digital communication system which can be used in conjunction with a fax communication system is a wireless code division multiple access (CDMA) system operating in the cellular or personal communication system (PCS) band or a GLOBALSTAR satellite communication system. These digital communication systems have inherent processing delays resulting from the large amount of digital signal processing and from transmission delays. These digital communication systems also employ central base stations to combine or multiplex signals from many communicating devices into a common transmission signal. The resultant overall delay can be both intolerably long and unpredictable.
Throughout the specification of the present invention, a syntax structure is maintained to clarify the discussion of the invention. In describing communications between two devices, the term `message` is used to denote a communication from a source device to a destination device. This `message` may or may not be retransmitted by the source device. The term `response` is used to denote a communication from the destination device to the source device as the result of the earlier transmitted `message`.
In a half-duplex communication system which utilizes a timing and synchronization scheme to avoid message collision, a source device desiring to communicate with a destination device on the same channel initiates the communication by sending out a message and waiting for a response from the destination device. After a predetermined length of time passes and if no response is received, the source device retransmits the message. This process is repeated for a specified number of times or until a response is received.
For a standard Group 3 fax communication system, the timing and synchronization between fax machines conform to behavior as specified in "ITU-T Recommendation T.30: Procedures for Document Facsimile Transmission in the General Switched Telephone Network", hereinafter referred to as the T.30 fax protocol. The T.30 fax protocol uses a number of modulation techniques for transmission of forward message data. In particular, parameter negotiation and handshaking between fax machines is accomplished using the modulation technique specified in "CCITT Recommendation V.21: 300 bps Duplex Modem Standard for use in the General Switched Telephone Network (GSTN)". The handshaking establishes the proper mode of communications between the fax machines.
For a T.30 fax system, a calling fax machine initiates a call by dialing the called fax machine and sending a calling tone (CNG). The called fax machine detects the incoming call and sends a called station identification tone (CED) back to the calling fax machine. The called fax machine then sends its digital identification signal (DIS) to the calling fax machine to inform the calling fax machine of its capabilities. Upon detection of the DIS signal, the calling fax machine sends a digital command signal (DCS) to inform the called fax machine of the capabilities the calling fax machine plans to use.
Other messages in addition to the above described initiation signals also take place between the fax machines during a call. For example, the training signals, information messages and termination messages are also part of a typical fax call.
A calling fax machine and a called fax machine send many messages between each other during a call. Messages are sent from either the calling fax machine or the called fax machine at various stages in a fax call. Since both calling and called fax machines can initiate messages, the discussion below describes the communications in terms of a source fax machine that initiates a message to a destination fax machine and a destination fax machine that reacts with a response back to the source fax machine without reference to calling or called fax machines. Some of the messages by the source fax machine must be repeated if no response is received for these messages.
The T.30 fax protocol specifies the procedure which must be followed when initiating a call between the fax machines. For example, the sequence and format of the CNG, CED, DIS, and DCS messages are specifically defined. The T.30 fax protocol also defines the messages which must be repeated if no response is received. Therefore, by monitoring the message format and having apriori knowledge of the signaling sequence, it is possible to determine which message will be repeated. A repeated message can be determined by analyzing the message and the state in a fax call in which it is received, as per the T.30 fax protocol.
To accommodate for unfavorable channel conditions, the T.30 fax protocol requires that certain unanswered messages between fax machines be repeated. If the source fax machine sends such a message to the destination fax machine, the source fax machine expects a response from the destination fax machine within a specified period of time. If no response is received after the specified period of time, the T.30 fax protocol requires the source fax machine to retransmit the message. The retransmissions continue until a response from the destination fax machine is received or an excessive number of attempts have been made.
The DIS and certain messages between the fax machines are repeated at a specified repetition interval if no response is detected. The T.30 fax protocol defines the shortest repetition interval within which a retransmission is allowed. For example, the T.30 fax protocol specifies the repetition interval for a fax machine operating in automatic mode to be 3.0 sec .+-.0.45 sec. This means that a fax machine conforming to the T.30 fax protocol will not retransmit a message within 2.55 sec of the prior message. Therefore, if such a fax machine receives a response within the shortest repetition interval of 2.55 sec, no collision will occur.
Under this T.30 fax timing scheme, long transmission delays in the communication channel can cause message collisions. In one scenario, the transmitting fax machine sends a message to the receiving fax machine and, because of the transmission delays, the response from the receiving fax machine takes more time than the repetition period to reach the transmitting fax machine. Since the transmitting fax machine does not receive the response in time, it retransmits the message. If the response from the receiving fax machine arrives at the same time the transmitting fax machine is retransmitting the message, a message collision results and the response will not be received by the transmitting fax machine.
The inability to account for unpredictable and long delays renders the communications between Group 3 fax machines on non-standard PSTN communication channels unreliable. A method is needed to prevent message collisions regardless of the amount of channel delay.